Due to the problems of slow speed and error drift in the positioning of large-scale long-sequence Unmanned Aerial Vehicle (UAV) images, a positioning algorithm of UAV images based on scene graph division was proposed according to the characteristics of UAV images. Firstly, the Global Positioning System (GPS) ancillary information was used to narrow the spatial search scope for feature matching, so as to accelerate the extraction of corresponding points. After that, visual consistency and spatial consistency were combined to construct the scene graphs, and Normalized Cut (Ncut) was used to divide them. Then, incremental reconstruction was performed to each group of scene graphs. Finally, all scene graphs were fused to establish a 3S scene model by Bundle Adjustment (BA). In addition, the GPS spatial constraint information was added to the cost function in the BA stage. In the experiments on four UAV image datasets, compared with COLMAP and other Structure From Motion (SFM) algorithms, the proposed algorithm has the positioning speed increased by 50%, the reprojection error decreased by 41%, and the positioning error was controlled within 0.5 m. Through the experimental comparison of algorithms with or without GPS assistance, it can be seen that BA with relative and absolute GPS constraints solves the problem of error drift, avoids the ambiguous results and greatly reduces positioning error.